class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        // 把烂橘子的坐标push进队列里
        // 并且统计一共有多少橘子
        int n = grid.size(), m = grid[0].size();
        int total = 0;
        queue<pair<int, int>> q;
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < m; j++)
            {
                // 统计橘子总数
                total += grid[i][j] > 0;

                // 把烂橘子坐标push进队列
                if(grid[i][j] == 2)
                    q.emplace(i, j);    // emplace会根据传入的参数自动构造一个相应的对象，这里就是pair
            }
        }

        // 如果矩阵一个橘子都没有，返回0
        if(total == 0)
            return 0;

        // 下面就是BFS(广度优先遍历)
        int minutes = -1;   // 由题意可知初始状态为0，所以这初始化为-1，进入while循环就会加1变成0

        // 统计烂橘子个数
        int rotten = 0;

        // 定义四个方向
        vector<pair<int, int>> dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

        // 判断方向是否合法且橘子是新鲜橘子，才有感染价值
        auto isValidPos = [&](int x, int y){
            return x >= 0 && y >= 0 && x < n && y < m && grid[x][y] == 1;
        };

        while(!q.empty())
        {
            // 枚举每个烂橘子，并把他们关联的(上下左右)的新鲜橘子搞烂
            int size = q.size();

            minutes++;
            rotten += size;

            for(int i = 0; i < size; i++)
            {
                auto [x, y] = q.front();
                q.pop();
                for(int j = 0; j < 4; j++)
                {
                    if(isValidPos(x + dirs[j].first, y + dirs[j].second))
                    {
                        grid[x + dirs[j].first][y + dirs[j].second] = 2;
                        q.emplace(x + dirs[j].first, y + dirs[j].second);
                    }
                }
            }
        }

        // 最后看腐烂的橘子是不是等于之前统计的总数
        // 如果等于，说明全都感染了，返回分钟数
        // 如果不相等，说明还剩一些没被感染，返回-1
        return total == rotten ? minutes : -1;
    }
};